Reed-Solomon codes are commonly used error correction codes. Some example applications include magnetic and optical data storage, wireline and wireless communications, and satellite communications. A Reed-Solomon code (n, k) over a finite field GF(q) satisfies n<q and achieves the maximally separable distance, i.e., d=n−k+1.
Chase-type decoders are a group or type of decoders of Reed-Solomon encoded data. In general, a Chase decoder flips and/or erases one or more (e.g., hard) bits prior to performing a Chien search. A Chien search (in general) locates the roots of a polynomial and when applied to an error locator polynomial is used to determine error locations since the roots of an error locator polynomial correspond to error locations. In some cases, an error locator polynomial passed to a Chien search may be incorrect (e.g., because the errors exceeded the error correction capability of a code). By flipping and/or erasing one or more bits prior to the Chien search, the correct error locator polynomial may be generated and passed to the Chien search. It would be desirable to develop new Chase-type decoders that are faster than existing Chase-type decoders.